package com.example.lib5.sort.test;

import java.util.Arrays;

public class InsertSort {
    public static void main(String[] args) {
        int[] arr = {101, 34, 35, 1};
        insertSortE(arr);
        System.out.println(Arrays.toString(arr));
    }

    private static void insertSort(int[] arr) {
        /**
         * 第一轮排序
         * 101,34,119,1 ---->34,101,119,1
         */
        //获取第一个要插入的值
        for (int i = 1; i < arr.length; i++) {
            int insertVal = arr[i];
            //获取第一个插入的值得前一个索引
            int insertIndex = i - 1;
            //while循环，前一个>=0且将第一个插入的值与前面的数据进行比较，小于就交换位置
            while (insertIndex >= 0 && insertVal < arr[insertIndex]) {
                arr[insertIndex+1] = arr[insertIndex];
                insertIndex--;
            }
            arr[insertIndex + 1] = insertVal;
        }

    }
    private static void insertSortC(int[] arr){
        //
        for (int i = 1; i < arr.length; i++) {
            //插入的值，插入值得前一个
            int insertValue=arr[i];
            int insertIndex=i-1;
            //比较大小，如果insVal大，就值节放置再哪里，不用改变，如果小的话，就找插入点
            if (arr[insertIndex]<arr[insertIndex]&&insertIndex>=0){
                arr[insertIndex+1]=arr[insertIndex];//后一个等于前一个
                insertIndex--;//插入的点前移
            }
            arr[insertIndex+1]=insertValue;
        }
    }
    private static void insertSortD(int[] arr){
        for (int i = 1; i < arr.length; i++) {
            //获取查询的前一个数组的坐标
            int insertIndex=i-1;
            int insertValue = arr[i];
            while (insertIndex>=0&&arr[insertIndex]>insertValue){
                arr[insertIndex+1]=arr[insertIndex];
                insertIndex--;
            }
            arr[insertIndex+1]=insertValue;

        }
    }
    private static void insertSortE(int[] arr){
        for (int i = 1; i < arr.length; i++) {
            //假设是插入值的前一个index
            int insertIndex=i-1;
            //插入的值
            int insertValue=arr[i];
            //如果插入的值大于前一个，就啥也不用做；如果小于的话，前一个值后移；继续以前前个比较
            while (insertIndex>=0&&arr[insertIndex]>insertValue){
                arr[insertIndex+1]=arr[insertIndex];
                insertIndex--;
            }
            arr[insertIndex+1]=insertValue;
        }
    }
    private static void insertSortF(int[] arr){
        if (arr==null||arr.length<=0) {
            System.out.println("队列无需排序");
        }
        for (int i = 1; i < arr.length; i++) {
            //假设插入点为前一个
            int insetIndex=i-1;
            //要插入的值
            int insetValue=arr[i];
            while (insetIndex>=0&&insetValue<arr[insetIndex]){
                arr[insetIndex+1]=arr[insetValue];
                insetIndex--;
            }
            arr[insetIndex+1]=insetValue;
        }
    }
}
